#include<iostream>
#include<vector>
#include<string>
using namespace std;

// 构建NEXT数组
void getnext(string& t,vector<int>& next)
{
	int j,k;
	
	// j遍历t，k记录t[0:j-1]的最长公共子序列
	j=0; k=-1;
	
	// 设置next[0]值
	next[0]=k;
	
	// 求t所有位置的next值
	while (j<t.size()-1)
	{
		// k为-1或比较的字符相等时
		if (k==-1 || t[j]==t[k])
		{
			j++; k++; // j、k依次移到下一个字符
			next[j]=k; // 设置next[j]为k
		}
		
		// k回退
		else  k=next[k];
	}
}

// 记录比较次数
int cnt=0;

// 字符串匹配 -- KMP算法
int KMP(string s, string t)
{
	int n=s.size();
	int m=t.size();
	
	// 构造NEXT数组
	vector<int> next(m, -1);
	getnext(t, next);
	
	// 指向两字符串的指针
	int i=0, j=0;
	
	while(i<n && j<m)
	{
		// 更新比较次数
		cnt++;
		
		// 字符匹配，i和j同时向后移动
		if (j==-1 || s[i]==t[j])
		{
			i++;
			j++;
		}
		
		// 字符不匹配
		else
			j=next[j]; // j寻找之前匹配的位置	}
	
	// t是s的子串
	if (j>=m)
		return i-t.size();
		
	// 不是子串
	else
		return -1;
}

int main()
{
	// 两个字符串
	string s="aaaabc";
	string t="aab";

	// 打印匹配结果
	printf("%d\n",KMP(s,t));
	
	// 打印比较次数
	printf("cnt=%d\n",cnt);
	return 0;
}
